/*
XPTracker - Alternative Agile Tracking Tool
Copyright (C) 2006-2009  Stephen Starkey

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
*/
package org.xptracker.util;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Implementation of Longest Common Subsequence shamelessly stolen from an Intro to CS course at Princeton:
 * http://www.cs.princeton.edu/introcs/96optimization/Diff.java.html
 */
public class Diff<T extends Comparable> {
  private static Log log = LogFactory.getLog(Diff.class);

  private Class<T> diffClass;
  private T[] leftLines;
  private T[] rightLines;
  private int leftLen;
  private int rightLen;

  public Diff(Class<T> diffClass, T[] leftLines, T[] rightLines) {
    this.diffClass = diffClass;
    this.leftLines = leftLines;
    this.rightLines = rightLines;

    leftLen = leftLines.length;
    rightLen = rightLines.length;
  }

  public List<Segment<T>> computeDifferences() {
    int[][] opt = new int[leftLen + 1][rightLen + 1];

    // Precalculate differences.
    for (int i = leftLen - 1; i >= 0; i--) {
      for (int j = rightLen - 1; j >= 0; j--) {
        if (leftLines[i].equals(rightLines[j])) {
          opt[i][j] = opt[i + 1][j + 1] + 1;
        } else {
          opt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]);
        }
      }
    }

    int i = 0;
    int j = 0;

    LinkedList<Segment<T>> segments = new LinkedList<Segment<T>>();
    while (i < leftLen && j < rightLen) {
      if (leftLines[i].equals(rightLines[j])) {
        addCommon(segments, leftLines[i]);
        i++;
        j++;
      } else if (opt[i + 1][j] >= opt[i][j + 1]) {
        addLeft(segments, leftLines[i++]);
      } else {
        addRight(segments, rightLines[j++]);
      }
    }

    // Dump the rest of the different lines from one side or the other if the last
    // bits are uneven.
    while (i < leftLen || j < rightLen) {
      if (i == leftLen) {
        addRight(segments, rightLines[j++]);
      } else if (j == rightLen) {
        addLeft(segments, leftLines[i++]);
      }
    }

    return segments;
  }

  private void addLeft(LinkedList<Segment<T>> segments, T leftLine) {
    log.debug("< " + leftLine);
    if (!segments.isEmpty() && !segments.getLast().isCommon()) {
      ((DiffSegment<T>) segments.getLast()).addLeft(leftLine);
    } else {
      segments.add(new DiffSegment<T>(diffClass, leftLine, null));
    }
  }

  private void addRight(LinkedList<Segment<T>> segments, T rightLine) {
    log.debug("> " + rightLine);
    if (!segments.isEmpty() && !segments.getLast().isCommon()) {
      ((DiffSegment<T>) segments.getLast()).addRight(rightLine);
    } else {
      segments.add(new DiffSegment<T>(diffClass, null, rightLine));
    }
  }

  private void addCommon(LinkedList<Segment<T>> segments, T line) {
    log.debug("C " + line);
    if (!segments.isEmpty() && segments.getLast().isCommon()) {
      ((CommonSegment<T>) segments.getLast()).addLine(line);
    } else {
      segments.add(new CommonSegment<T>(diffClass, line));
    }
  }

  public static abstract class Segment<U extends Comparable> {
    private Class<U> diffClass;

    protected Segment(Class<U> diffClass) {
      this.diffClass = diffClass;
    }

    public abstract boolean isCommon();

    public U[] getCommonLines() {
      return null;
    }

    public U[] getLeftLines() {
      return null;
    }

    public U[] getRightLines() {
      return null;
    }

    @SuppressWarnings({"unchecked"})
    protected U[] toArray(List<U> lines) {
      return (U[]) lines.toArray((Object[]) Array.newInstance(diffClass, 0));
    }
  }

  private static class CommonSegment<U extends Comparable> extends Segment<U> {
    private List<U> lines;

    public CommonSegment(Class<U> diffClass, U firstLine) {
      super(diffClass);
      lines = new ArrayList<U>();
      lines.add(firstLine);
    }

    public boolean isCommon() {
      return true;
    }

    public void addLine(U line) {
      lines.add(line);
    }

    public U[] getCommonLines() {
      return toArray(lines);
    }
  }

  private static final class DiffSegment<U extends Comparable> extends Segment<U> {
    private List<U> leftLines;
    private List<U> rightLines;

    public DiffSegment(Class<U> diffClass, U left, U right) {
      super(diffClass);
      leftLines = new ArrayList<U>();
      rightLines = new ArrayList<U>();

      addLeft(left);
      addRight(right);
    }

    private void addRight(U right) {
      if (right != null) {
        rightLines.add(right);
      }
    }

    private void addLeft(U left) {
      if (left != null) {
        leftLines.add(left);
      }
    }

    public boolean isCommon() {
      return false;
    }


    public U[] getLeftLines() {
      return toArray(leftLines);
    }

    public U[] getRightLines() {
      return toArray(rightLines);
    }
  }
}
